package com.maishi.programmer.jainzhioffer;

/**
 * Created by brossdong on 2018/4/12.
 * 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。
 * 输入一个数组,求出这个数组中的逆序对的总数P。
 */
public class TestProblem51 {

    public static int InversePairs(int [] array) {

        if (array.length <= 1 || array == null) return 0;
        //创建一个array.length大小的数组
        int[] copy = new int[array.length];
        for (int i = 0;i < array.length;i++) {
            copy[i] = array[i];
        }
        return mergeCount(array,copy,0,array.length - 1);
    }

    public static int mergeCount (int[] array,int[] copy,int start,int end) {
        if (start == end) {
            copy[start] = array[start];
            return 0;
        }
        //分治
        int mid = (start + end) >> 1;
        int leftCount = mergeCount(copy,array,start,mid);
        int rightCount = mergeCount(copy,array,mid + 1,end);

        //初始化前半段最后一个数字的下标
        int i = mid;
        //初始化后半段最后一个数字的下标
        int j = end;
        //辅助数组复制的数组的最后一个数字的下标
        int index = end;
        //计算逆序对
        int count = 0;

        while (i >= start && j >= mid + 1) {
            if (array[i] > array[j]) {
                copy[index--] = array[i--];
                count += j - mid;
            } else {
                copy[index--] = array[j--];
            }
        }
        for (;i >= start;i--) {
            copy[index--] = array[i];
        }
        for(;j >= mid + 1;j--){
            copy[index--] = array[j];
        }

        return leftCount + rightCount + count;
    }

    public static void main(String[] args) {
        int inversePairs = InversePairs(new int[]{1,2,3,4,5,6,7,0});
        System.out.println(inversePairs);
    }
}
